Nguyen Dao
May 7, 1998
CompSci. 201
Cache:
Cache is a special memory used to decrease the memory access time. The cache’s effectiveness is based on locality of reference.
Memory access time: the time elapses between the initiation of an instruction and the completion of that instruction. The time between a Read-signal and a Memory-Function-Complete signal is an example of a memory access time.
Locality of reference: refers to the property of a program when many instructions in localized area of the program are executed repeatedly (e.g. loops, nested-loop, recursive procedures, etc.), and the rest is accessed/used relatively infrequently.
To execute a program, the program itself has to be in Primary Memory, which is slower compared to Cache Memory. So by storing recently executed-instruction (temporal locality)/or the instructions close to the recently executed instruction (spatial locality) in the Cache Memory the total memory access time can be decreased because those instructions are likely to be used/accessed by the program again/next.
The Cache is organized by what is called a set of hardware-control circuitry. The Cache is divided into blocks that correspond to blocks in Primary Memory, and they all are equal in size (always in power of two) that is fixed by the hardware. Correspondence of blocks between Cache and Primary Memory is determined by cache mapping function (direct, associative, set-associative mapping).
When a word is referenced (e.g. by a program) the hardware check to see if it is in the cache first. If it is in the cache (called cache hit), then the referenced word can be transferred from the Cache instead of the Primary Memory thus will be faster. If the referenced-word is not in the Cache (called cache miss), then a block containing that referenced-word has to be transferred from Primary Memory to both where it’s needed (CPU) and to the Cache, so that next time when it’s needed it can be transferred from the Cache directly.
Cache hit can be subdivided into Read hit & Write hit, and Cache miss can be subdivided into Read miss & Read hit.
Read hit:
Main Memory is not involved.
Write hit:
There are two techniques write-through protocol and write-back protocol.
Write-through:
Word in Cache location and Main Memory location are updated simultaneously.
Write-back/Copy-back:
Block in Cache location is updated and marked as updated by the use of a dirty bit/modified bit. Main Memory location is updated (based on this dirty/modified bit) later when the block is evicted/removed to make room for a new block. This method is more complicated than write-through.
Read miss:
The block containing the referenced-word is copied from the main memory into the Cache, then the referenced-word is forwarded from the Cache to where it is needed (the CPU).
Write miss:
If the Write-through protocol is used: the information is written directly into memory.
If the Write-back protocol is used: the block containing the addressed/referenced word is brought into Cache, then the desired word is overwritten with the new information. Then later when this block is evicted the new information will replace the old information in Main Memory.
When the Cache is full and a memory word that is not in the Cache is referenced, then the Cache’s hardware control must decide which block in the Cache is to be evicted/removed to create space for a new block that contains the referenced-word. This decision of the hardware control depends on a collection of rules called replacement algorithm.
Direct mapping:
A block X of Main Memory is mapped onto the block X mod # of blocks available in Cache. For example, there are 128 blocks in Cache and plenty more in Memory, then blocks from 0-127 in Memory will be mapped onto blocks 0-127 in Cache, and blocks from 128-255 in Memory will be mapped onto blocks 0-127 in ordered pairs (<0Mà 0C>, . . ., <127Mà 127C>, <128Mà 0C>, . . ., <255Mà 127C>, and so on).
To reference a word (data/instruction) the CPU sends out the address of where that word is in Main Memory. And that Memory Address has the following format:
Tag Block Word
|
5 bits |
7 bits |
4 bits |
Memory Address
Memory’s Tag is compared with Cache’s Tag:
Match: referenced word is in Cache at Block # 7bits
No Match: referenced word is not in Cache then the Cache block is evicted and replaced with the new block (from Memory) containing that word.
Cache
|
Tag |
Block 0 |
|
Tag |
Block 1 |
|
. |
. |
|
. |
. |
|
. |
. |
|
Tag |
Block 127 |
Along with the Tag there is also a valid bit that tells whether the block is in use in which case it’s set to 1.
Disadvantage: contention is possible, for instance Block 0 and Block 128 in Memory will be mapped to Block 0 in Cache. So we can waste a lot of time evicting Block 0 in Cache and replace it with Block 0, and Block 128 from Memory if there are two consecutive referenced-words with each one is contained in each of those two Blocks (0, 128) in Memory.
Main Memory
|
Block 0 |
|
Block 1 |
|
. |
|
. |
|
Block 127 |
|
Block 128 |
|
. |
|
. |
|
Block 255 |
|
Block 256 |
|
. |
|
. |
|
Block 4095 |
Pure-Associative mapping:
All Cache Blocks whose valid bit is one (set), then each of their Tags is compared to Memory Address’s Tag (in parallel):
Match: the referenced-word is in the Cache’s Block where its Tag matches Memory Address’s Tag.
No Match: the referenced-word is not Cache.
Tag Word
|
12 bits |
4 bits |
Main Memory Address
Tag = X exponent of the 2X Blocks (in this case 212).
Word = Y exponent of 2Y words in a Block.
Set-associative mapping:
The Cache is divided into sets containing a # of Blocks. Each Memory Address is then divided into three parts as follow:
Tag Set Word
|
6 |
6 |
4 |
Main Memory Address
Tag = X exponent of the 2X sets (in this case 26).
Set = X
Word = Y exponent of 2Y words in a Block.
Information at PM Address whose Set-field matches with the Set-field of Cache, will be stored in a Block of that Set. Within a Set, Pure-Associative mapping is used.
So, direct mapping is used to find the set, and pure-associative mapping is used to decide which Block of the Set will the new information stored in.
Cache
|
Set0 |
Tag |
Block 0 |
|
Set0 |
Tag |
Block 1 |
|
. |
. |
. |
|
. |
. |
. |
|
Set63 |
Tag |
Block 126 |
|
Set63 |
Tag |
Block 127 |
Main Memory
|
Block 0 |
|
Block 1 |
|
. |
|
. |
|
Block 127 |
|
Block 128 |
|
. |
|
. |
|
Block 255 |
|
Block 256 |
|
. |
|
. |
|
Block 4095 |
----------------------End of Cache Memory-------------------------